package 左哥算法.ch12滑动窗口与双端队列;

import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;

public class Ch01窗口最大值 {

    @Test
    public void test(){
        int[] ints = maxSlidingWindow(new int[]{1,3,1,2,0,5}, 3);
        System.out.println(Arrays.toString(ints));
    }

    Deque<Integer> deque=new LinkedList<>();
    int[] nums;
    int L=0,R=0;    //包含左边界，不包含右边界
    /**
     * 有一个大小为 k 的滑动窗口,每次向右移动一次，返回滑动窗口中的最大值 。
     * @param nums
     * @param k:大小为 k 的滑动窗口
     * @return
     */
    public int[] maxSlidingWindow(int[] nums, int k) {
        this.nums=nums;
        int[] res=new int[nums.length-k+1];
        for (int i = 0; i < k; i++) {   //扩容三次
            expand();
        }
        for (int i = 0; i <res.length; i++) {
            res[i]=nums[deque.peekFirst()];
            lessen();
            expand();
        }
        return res;
    }

    public void expand(){
        if (R<nums.length){
            while (!deque.isEmpty()&&nums[deque.peekLast()]<= nums[R]) { //队列不等于空且尾部元素小于新元素
                deque.pollLast();
            }
            deque.add(R);
            R++;
        }
    }
    public void lessen(){
        if (L<R){
            if (L==deque.peekFirst()){
                deque.pollFirst();
            }
            L++;
        }
    }
}